//
// Created by 高森森 on 2022/2/9.
//

#ifndef LEETCODE_SOLUTION26_H
#define LEETCODE_SOLUTION26_H
#include<iostream>
#include<vector>
#include <queue>
#include <cfloat>

using namespace std;


class Solution26 {
public:
    double maxProbability(int n, vector<vector<int>>& edges, vector<double>& succProb, int start, int end) {
        vector<vector<vector<double>>>graph(n);
        for(int i=0;i<edges.size();i++)
        {
            graph[edges[i][0]].push_back(vector<double>{(double)edges[i][1],succProb[i]});
            graph[edges[i][1]].push_back(vector<double>{(double)edges[i][0],succProb[i]});
        }
        queue<vector<double>>que;
        vector<double>ans(n,0);
        que.push(vector<double>{(double)start,1.0});
        while(!que.empty()){
            int len=que.size();
            for(int i=0;i<len;i++){
                auto node=que.front();
                que.pop();
                for(auto neigh:graph[node[0]]){
                    double dis=neigh[1]*node[1];
                        if(dis>ans[neigh[0]]){
                            ans[neigh[0]]=dis;
                            que.push(vector<double>{neigh[0],dis});
                        }
                }

            }
        }
        return ans[end];
    }

    double maxProbability2(int n, vector<vector<int>>& edges, vector<double>& succProb, int start, int end) {
        vector<vector<pair<double,int>>>graph(n);
        for(int i=0;i<edges.size();i++)
        {
            graph[edges[i][0]].push_back(make_pair(succProb[i],edges[i][1]));
            graph[edges[i][1]].push_back(make_pair(succProb[i],edges[i][0]));
        }
        priority_queue<pair<double,int>>que;
        vector<double>ans(n,0);
        que.push(make_pair(1.0,start));
        while(!que.empty()){
            int len=que.size();
            for(int i=0;i<len;i++){
                auto node=que.top();
                que.pop();
                for(auto neigh:graph[node.second]){
                    double dis=neigh.first*node.first;
                    if(dis>ans[neigh.second]){
                        ans[neigh.second]=dis;
                        que.push(make_pair(dis,neigh.second));
                    }
                }

            }
        }
        return ans[end];
    }
};


#endif //LEETCODE_SOLUTION26_H
